/**
 * Created by zhourh on 2018/10/18.
 *
 * 给定一个非负整数数组 A， A 中一半整数是奇数，一半整数是偶数。

 对数组进行排序，以便当 A[i] 为奇数时，i 也是奇数；当 A[i] 为偶数时， i 也是偶数。

 你可以返回任何满足上述条件的数组作为答案。



 示例：

 输入：[4,2,5,7]
 输出：[4,5,2,7]
 解释：[4,7,2,5]，[2,5,4,7]，[2,7,4,5] 也会被接受。


 提示：

 2 <= A.length <= 20000
 A.length % 2 == 0
 0 <= A[i] <= 1000


 */
public class SortArrayByParityII {

    public static void main(String[] args) {
        Printer.printIntArray(new SortArrayByParityII().sortArrayByParityII2(new int[]{4,2,5,7}));
    }

    public int[] sortArrayByParityII(int[] A) {
        if (A == null || A.length <= 0 || A.length % 2 != 0) {
            return A;
        }

        int[] odds = new int[A.length / 2];
        int[] evens = new int[A.length / 2];

        int oddIndex = 0;
        int evenIndex = 0;
        for (int i = 0; i < A.length; i++) {
            if (A[i] % 2 == 0) {
                evens[evenIndex++] = A[i];
            } else {
                odds[oddIndex++] = A[i];
            }
        }

        oddIndex = 0;
        evenIndex = 0;
        for (int i = 0; i < A.length; i++) {
            if (i % 2 == 0) {
                A[i] = evens[evenIndex++];
            } else {
                A[i] = odds[oddIndex++];
            }
        }

        return A;
    }

    public int[] sortArrayByParityII2(int[] A) {
        if (A == null || A.length <= 0 || A.length % 2 != 0) {
            return A;
        }

        int oddIndex = 1;
        int evenIndex = 0;
        int[] result = new int[A.length];

        for (int a : A)  {
            if (a % 2 == 0) {
                result[evenIndex] = a;
                evenIndex += 2;
            } else {
                result[oddIndex] = a;
                oddIndex += 2;
            }
        }

        return result;
    }
}
